
from Code_Link_02 import ListNode
from Code_Link_02 import printLink

''' 
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
删除链表的倒数第N个节点，返回头节点
1->2->3->4->5  n=2 1<=n<=sizes
1->2->3->5 删除倒数第2个节点4
'''
def l19(head:ListNode,n):
    dummy_head = ListNode(next = head) #设置虚拟头节点，便于删除的节点是头节点的场景
    second = dummy_head
    first = dummy_head
    pre = dummy_head
    size = num = 0
    while first:
        while second.next:#size总长度，num正向节点，删除的是第num+1个节点（从1开始数）
            second = second.next
            size += 1
            #print("size:",size)
            num = size - n
        if size == 1:return ListNode() #只有一个节点，返回空节点
        if num >= 0:
            pre = first #得到删除节点的前一个节点
            first = first.next #向后移动到该删除的节点
            num -= 1
        else:
            if first.next == None :
                pre.next = None #删除的是尾节点，尾节点的前置节点的下一节点置为空
                printLink(dummy_head.next)

            else:
                printLink(dummy_head.next)
                pre.next = first.next
            return dummy_head.next

    pass

if __name__ == '__main__':
    link7 = ListNode(7)
    link6 = ListNode(6,link7)
    #link5 = ListNode(5,link6)
    link5 = ListNode(5)
    link4 = ListNode(4,link5)
    #link4 = ListNode(4)
    link3 = ListNode(3,link4)
    #link3 = ListNode(3)
    link2 = ListNode(2,link3)
    link1 = ListNode(1,link2)
    #printLink(link1)
    res = l19(link7,1)
    printLink(res)

    #l206(link6)
    pass